package org.sunny.sort;

/**
 * 二分搜索
 *
 * @author Sunny
 * @date 2020/8/21
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 5, 6, 7, 9, 11};

        System.out.println(indexOf(arr, 5));
        System.out.println(searchIndex(arr, 5));
    }

    /**
     * 二分搜索
     *  假设在 [begin, end) 范围内搜索某个元素 v，mid == (begin + end) / 2
     *
     *  ◼ 如果 v < m，去 [begin, mid) 范围内二分搜索
     *  ◼ 如果 v > m，去 [mid + 1, end) 范围内二分搜索
     *  ◼ 如果 v == m，直接返回 mid
     *
     * @param arr 有序数组
     * @param v 待查找元素
     * @author Sunny
     * @date 2020/8/21
     */
    public static int indexOf(int[] arr, int v) {
        if (arr == null || arr.length == 0) return -1;

        int begin = 0;
        int end = arr.length;

        while (begin < end) {
            int mid = (begin + end) >> 1;

            if (v < arr[mid]) {
                end = mid;
            } else if (v > arr[mid]) {
                begin = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    /**
     * 利用二分搜索找出 v 应该在 arr 数组中插入的位置
     *  二分搜索返回的插入位置：第1个大于 v 的元素位置
     *
     * @param arr 有序数组
     * @param v 待插入元素
     * @author Sunny
     * @date 2020/8/21
     */
    public static int searchIndex(int[] arr, int v) {
        if (arr == null || arr.length == 0) return -1;

        int begin = 0;
        int end = arr.length;

        while (begin < end) {
            int mid = (begin + end) >> 1;

            if (v < arr[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}
